The present invention relates to the field of raster shape synthesis, i.e., the creation of shapes for display on a raster display device. More specifically, in one embodiment of the invention, multi-level raster shapes are converted into bi-level raster shapes for display on raster display devices, while preserving visual cues available with multi-level raster shapes.
A display device, as used herein, is any device which displays an image, such as a computer monitor, a television, a printer, or an image processor whose eventual output is an image on a display device.
A raster display device is a display device in which an image is represented when an array of picture elements (pixels), usually in a two-dimensional rectangular array with pixels uniformly spaced over a display surface, are colored with pixel colors to suggest the image. The image produced by a raster display device is said to be "pixelated" because the image, upon close inspection, comprises finite pixels, each colored a uniform solid color. Compare this with vector display devices and non-electronic displays, such as an oil painting, which do not exhibit pixelation.
A raster display device is characterized for our purposes by the dimensions of its rectangular array of pixels in its display surface, and the color values possible for each pixel. Thus, an image can be represented by a data set having an element associated with each pixel of the display device, where an element would have an associated X and Y coordinate position, identifying the pixel to which it belongs, and a pixel color value. In the present context, "image" refers to such a data set. Consequently, the following discussion of images will apply equally well to those images which are manipulated by image processors and those images which are displayed on display surfaces of raster display devices which have display surfaces.
While sometimes pixels are thought of as points, they may also be thought of as finite areas defined by the point which is the pixel's position and the spacing between pixels, so as to fully map the area of a display surface onto the pixels. For example, where the pixel array is a rectangular array, the pixels define a rectangular grid, and the rectangles formed by the grid lines could be used as the pixels' finite areas. In a physical display device, of course, the boundary of a pixel might not be so exact, with pixels sometimes occupying a vaguely defined area and possibly overlapping adjacent pixels'areas. Such is the case with laser printers, where a pixel is a point on a page which is colored by placing a finite amount of solid ink at the pixel position and pressing it into the page, merging with adjacent pixels in the process.
A raster device with a two-dimensional display surface can display a two-dimensional image of virtually any object, by coloring the pixels of the raster device's display surface so as to collectively suggest the desired object's shape and color. It is this flexibility, that any device can represent any object, which has made raster devices the preferred output devices for today's computers and many consumer products. Dot matrix printers, laser printers, facsimile machines, video game displays, high-definition televisions, and computer monitors are all examples of raster display devices.
Suppose a raster display is used to display an object such as a filled-in black circle on a white background. To display the circle, the circle and the background are mapped onto the display's array of pixels, and the pixels which correspond most closely to the circle are determined. Once pixels representative of the circle are identified, then those pixels are assigned a pixel color value corresponding to black and the other pixels are assigned a pixel color value corresponding to white.
Because the pixel array is made up of a finite number of pixels each of which can be assigned only one pixel color value, the circle can be displayed only approximately--a close inspection will reveal jagged edges. One way of smoothing the jagged edges is to allow pixels whose pixel area is only partially enclosed within the boundary of the circle to be colored a color between white and black according to how much pixel area is within the circle. This is sometimes called anti-aliasing, where aliasing is the "jagged edge" effect caused by the finite size of the pixels. See, for example, the article by N. Negroponte, entitled "Aliasing: The Blind Spot of the Computer Industry", Wired, January 1994, p. 152, for a description of the beneficial effects of anti-aliasing.
The process of generating an image that includes the depiction of an object can be divided into three steps: 1) placing the outline of the object over the pixel array of the image, 2) assigning a coverage value to each of the pixels of the image which describes what fraction of the pixel is covered by the outline, and 3) changing the color values of pixels covered by the object outline so they depict the object superimposed on whatever scene the image was depicting. Step 3 is usually performed by leaving pixels outside the object unaffected, assigning the color of the object to pixels that are completely inside the outline and assigning a mixture of the object color and their current color to those pixels that are only partially covered by the outline.
In our example of the black circle, we assumed that all pixels would be classified into inside and outside. This is a common assumption that makes step 3 simpler to perform since the pixels outside the circle would retain their color (white) and those inside the circle would be changed to the object color (black). If we had allowed pixels to be considered partially inside the outline, the color of those pixels would have to be changed to a shade of gray computed by mixing black and white in proportion to the fractions of the pixel covered and not covered by the outline. Because mixing colors is not a simple operation in some situations, forcing coverage values to be either completely inside or completely outside is a common shortcut.
It is a common occurrence that an object is shown in multiple positions in an image, possibly in different colors. In that case, the coverage values computed in step 2 need not be recomputed from scratch for each instance of the object. Typically, the coverage values are computed for a bounding rectangle, where a bounding rectangle is a rectangular array of pixels that includes all those pixels touched by the object's outline. The data set computed in this manner, comprising of a rectangular array of coverage values, can then be used to add the object to an image in different positions and with different colors, by appropriately mapping the coverage values of the bounding rectangle to the pixels of the image while performing step 3. The coverage values for the bounding rectangle of the object therefore represent the shape of the object and form what is described herein as a "raster shape". The bounding shape need not be a rectangle, but rectangles are the easiest bounding box to deal with.
If each pixel in a raster shape is allowed to have only one of two coverage values (each representing a choice between inside and outside) as in the example of our circle, the raster shape is said to be bi-level. When pixels are not restricted in this manner, the raster shape is said to be multi-level. The coverage values of a multi-level raster shape are usually given in the range 0-1. Because the coverage value of a pixel represents the fraction of the pixel covered by the object's outline, pixels completely outside the outline will have a coverage value of 0, those completely inside a coverage value of 1, and pixels on the boundary coverage values between 0 and 1.
Compared with bi-level raster shapes, multi-level raster shapes are harder to compute, require more memory to store, and are more difficult to use because they require the blending of colors. However, in exchange for the extra effort, they produce smoother shapes and better visual results overall. Nonetheless, because it is impossible to use multi-level raster shapes in devices that are not capable of representing different color tones or shades, bi-level raster shapes have applications even when the extra cost of using multi-level raster shapes is acceptable.
Prior art methods of computing bi-level raster shapes include estimating whether the coverage value for each pixel is closer to 0 or to 1 and assigning to it one of the two values. Although generally more efficient and less precise, these methods are logically equivalent to first computing a multi-level raster shape of the same size and then rounding the resulting coverage values to obtain bi-level values. FIGS. 1-4 illustrate two problems which occur bi-level shapes are computed in this manner, the problem of drop-outs and the problem of stem width aliasing.
FIG. 1 illustrates the difference between a multi-level raster shape and a bi-level raster shape. FIG. 1 shows a bounding box 10 enclosing a multi-level raster shape 14 and a bounding box 20 enclosing a bi-level raster shape 16 each or which is overlaid on a pixel grid 12. Each raster shape 14, 16 is a representation of the character "o", with the coverage values of each pixel represented graphically by the shade of gray that would be produced by using the coverage value to mix the black color of the letter with the white color of the background. In raster shape 16, it being bi-level, the coverage values are limited to 0 or 1, so pixels are colored either white or black. In raster shape 14, darker shades of gray represent higher coverage values.
Because of the resolution limitations of pixel grid 12, up close, the raster shapes do not look like the character. However, from a distance, the raster shapes do look like the character, with raster shape 14 tending to lose its jagged edges at a shorter distance than raster shape 16. As should be apparent, raster shape 16 can be derived from a description of the outline of the character "o" mapped onto pixel grid 12, or raster shape 16 can be generated from raster shape 14, by simply rounding each coverage value in raster shape 14 to either 0 or 1.
This rounding is illustrated in FIG. 2. FIG. 2 also shows bounding boxes 10, 20, but with the coverage values shown numerically instead of graphically. An outline 24 of the character "o" from which the coverage values were derived is also shown overlaid on pixel grid 12. Outline 24 is two solid curves, although they appear in FIG. 2 (and in other figures) to be broken by white space surrounding the pixel values; this is an artifact caused by white space being added to make the numbers easier to read.
As FIG. 2 shows, bi-level raster shape 16 (in bounding box 20) is generated from multi-level raster shape 14 (in bounding box 10) by changing coverage values of less than 0.5 to 0 and coverage values of 0.5 or more to 1. While this often leads to acceptable results, FIG. 3 shows one problem which occurs with this derivation.
FIG. 3 shows two raster shapes, one multi-level (26) and the other bi-level (28), generated from an outline of the character "o" taken from a font different than the font used for the "o" in FIG. 2. The character in FIG. 3 is contained in four bounding boxes 31, 32, 33 and 34. Bounding boxes 31 and 33 (left column) are overlaid with outline 30 and show coverage values numerically, while bounding boxes 32 and 34 (right column) show coverage values as gray levels. Bounding boxes 31 and 32 (top row) contain multi-level raster shape 26, while bounding boxes 33 and 34 (bottom row) contain bi-level raster shape 28.
A particular pixel 40, shown in each bounding box in FIG. 3 will now be examined. In multi-level raster shape 26, the coverage value for pixel 40 is 0.3, meaning that three-tenths of the pixel are covered by the outline. Consequently, in the bi-level raster shape, the coverage value of pixel 40 is 0, which leaves the gap in the character shown in bounding box 34. In raster shapes 26 and 28, although the curves of the character are apparently lost, they are regained as the distance between the raster shape and the viewer's eye increases, and this occurs earlier and more convincingly in raster shape 26 than in raster shape 28. This improvement does not necessarily occur for all important visual characteristics of the shapes, however.
For example, the original shape was connected and had a central opening. Raster shape 28 viewed from a distance, however, does not appear connected and appears instead as a pair of parentheses. The lack of connectivity of the bi-level raster shape is a result of blindly rounding the multi-level coverage values. The problem of broken connectivity in bi-level raster shapes exhibited by raster shape 28, is known as the "drop-out" problem.
FIG. 4 illustrates another problem with blindly rounding multi-level raster shapes to generate bi-level raster shapes. FIG. 4 shows four bounding boxes 50, 52, 54 and 56 in which an outline 58 of the character "N" is rasterized. Bounding boxes 50 and 54 (left column) are overlaid with outline 58 and show coverage values numerically, while bounding boxes 52 and 56 (right column) show coverage values as gray levels. Bounding boxes 50 and 52 (top row) contain a multi-level raster shape 60, while bounding boxes 54 and 56 (bottom row) contain a bi-level raster shape 62.
One edge of outline 58, edge 64, is a vertical edge which covers 40% of each pixel in a pixel row 66. Therefore, in multi-level raster shape 60, the pixels of row 66 are shaded with a 40% gray level, whereas the pixels of row 66 are white in bi-level raster shape 62, since 0.4 rounds to zero. This rounding also causes the loss of a visual cue, but one of a different sort. When viewing multi-level raster shape 60 from a distance, a viewer's eye would place edge 64 somewhere in the middle of row 66, whereas when viewing bi-level raster shape 62 from a similar distance, a viewer's eye would place edge 64 at the left side of row 66, since row 66 is all white. This erases the visual cue of symmetry between the two stems of the letter "N" thereby creating an instance of the general problem known as "stem width aliasing".
The prototypical solutions to the drop-out and stem width aliasing problems are described in R. Hersch and C. Betrisey, "Advanced Grid Constraints: Performance and Limitations" Raster Imaging and Digital Typography II, R. A. Morris and J. Andre eds., pp. 190-204 (Cambridge University Press, Cambridge 1991).
Efficient methods and apparatus for computing multi-level raster shapes from analytic descriptions of outlines is described in U.S. Pat. No. 5,438,656 (Application Ser. No. 08/070,135, filed in Jun. 1, 1993 ; [hereinafter "the multi-level raster shape generator"]; commonly owned by the assignee of the present application, incorporated herein for all purposes).